package leetcode.editor.cn;

//Java：在排序数组中查找元素的第一个和最后一个位置
public class FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        // TO TEST
    }

    /**
     * 错误思路：虽然是有序的数组，但是有重复数据，所以不能用二分法。
     * 答：错误，因为这个题找的不是一个值，而是两个值，只需要对左右两边都用一次二分法就好。
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return new int[]{-1, -1};
            }
            int startIndex = findStartIndex(nums, target);
            int endIndex = findEndIndex(nums, target);
            return new int[]{startIndex, endIndex};
        }

        /**
         * 问题1：为什么之前的二分法都是>、<为什么这里是target >= nums[mid]?
         * 答：二分法中，如果目标值大于中间值，left=mid+1;因为它找的是右侧的那个目标值，所以左侧相等的时候，并不敏感，所以先记录下第一个这个值，
         * 然后继续加大left找右侧的即可。下次判断的时候，虽然已经找到了一个，但是依然需要继续往右。
         * 直到最后在右侧找到目标值的时候，记录下标
         * 问题2：为什么
         *
         * @param nums   数组
         * @param target 目标值
         * @return int 右侧满足target的下标
         */
        private int findEndIndex(int[] nums, int target) {
            int index = -1;
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (target >= nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
                if (nums[mid] == target) index = mid;
            }
            return index;
        }

        /**
         * 问题2：为什么之前的二分法都是>、<为什么这里是target <= nums[mid]?
         * 答：二分法中，如果目标值小于中间值， right = mid - 1;;因为它找的是左侧的那个目标值，所以左侧相等的时候，并不敏感，所以先记录下第一个这个值，
         * 继续加大left找右侧的即可。下次判断的时候，虽然已经找到了一个，但是依然需要继续往左。
         * 直到最后在右侧找到目标值的时候，记录下标
         *
         * @param nums   数组
         * @param target 目标值
         * @return int 左侧满足target的下标
         */
        private int findStartIndex(int[] nums, int target) {
            int index = -1;
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
                if (nums[mid] == target) index = mid;
            }
            return index;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}